/*
 * @lc app=leetcode.cn id=130 lang=c
 *
 * [130] 被围绕的区域
 */

// @lc code=start

int parent[40002];

int find(int x) {
    if (parent[x] != x) {
        parent[x] = find(parent[x]);
    }
    return parent[x];
}

void unionTwo (int x, int y) {
    int xR = find(x);
    int yR = find(y);
    if (xR != yR) {
        parent[xR] = yR;
    }
}

int connect(int x, int y) {
    return find(x) == find(y);
}

void solve(char** board, int boardSize, int* boardColSize){
    int l = boardColSize[0] * boardSize + 1;
    int dummy = boardColSize[0] * boardSize;
    for (int i = 0; i < l; ++i) {
        parent[i] = i;
    }

    for (int i = 0; i < boardSize; ++i) {
        if (board[i][0] == 'O') {
            unionTwo(dummy, i * boardColSize[0]);
        }
        if (board[i][boardColSize[0] - 1] == 'O') {
            unionTwo(dummy, i * boardColSize[0] + boardColSize[0] - 1);
        }
    }

    for (int i = 0; i < boardColSize[0]; ++i) {
        if (board[0][i] == 'O') {
            unionTwo(dummy, i);
        }
        if (board[boardSize - 1][i] == 'O') {
            unionTwo(dummy, (boardSize - 1) * boardColSize[0] + i);
        }
    }

    int d[][2] = {
        {1, 0},
        {0, 1},
        {-1, 0},
        {0, -1}
    }; 

    for (int i = 1; i < boardSize - 1; ++i) {
        for (int j = 1; j < boardColSize[0] - 1; ++j) {
            if (board[i][j] == 'O') {
                // printf("a");
                for (int k = 0; k < 4; ++k) {
                    int x = i + d[k][0];
                    int y = j + d[k][1];
                    if (board[x][y] == 'O') {
                        // printf("+");
                        unionTwo(i * boardColSize[0] + j, x * boardColSize[0] + y);
                    }
                }
            }
        }
    }

    for (int i = 1; i < boardSize - 1; ++i) {
        for (int j = 1; j < boardColSize[0] - 1; ++j) {
            if (board[i][j] == 'O') {
                if (!connect(i * boardColSize[0] + j, dummy)) {
                    board[i][j] = 'X';
                }
            }
        }
    }


}
// @lc code=end

